package chapter04_RecursionAndDynamic;

/**
 * 描述：
 *      最长公共子串
 * @author hl
 * @date 2021/6/16 14:36
 */
public class Lcst {

    public static void main(String[] args) {
        Lcst lcst = new Lcst();
        String str1 = "1AB2345CD";
//        String str1 = "abcde";
        String str2 = "12345EF";
//        String str2 = "bebcd";
        String res = lcst.lcst1(str1, str2);
        String res2 = lcst.lcst2(str1, str2);
        System.out.println(res);
        System.out.println(res2);
    }

    public String lcst1(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return null;
        }
        int[][] dp = getDp1(str1, str2);
        int max = 0, ends = 0;
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    ends = i;
                }
            }
        }
        return str1.substring(ends - max + 1, ends + 1);
    }

    /**
     * 构建一个二维数组dp，dp[i][j]表示以str1[i]结尾的子串s1，与以str2[j]记为的子串s2相同的最大长度
     * @param str1
     * @param str2
     * @return
     */
    public int[][] getDp1(String str1, String str2){
        int m = str1.length();
        int n = str2.length();
        int ends = 0, max = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (str1.charAt(i) == str2.charAt(0)) {
                dp[i][0] = 1;
            }
        }
        for (int j = 0; j < n; j++) {
            if (str1.charAt(0) == str2.charAt(j)) {
                dp[0][j] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp;
    }

    /**
     * 优化空间
     * 根据上面的解法可知，每个位置(i,j)的结果只依赖于(i-1,j-1)位置的结果，因此如果我们按照斜线的生成，
     * 只需要一个额外的变量就可以保存之前生成的值，然后在遍历的过程中得到最大的长度和最大子串的位置
     * @param str1
     * @param str2
     * @return
     */
    public String lcst2(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return null;
        }
        int max = 0, ends = 0, preLen = 0;
        //(row,col)表示条斜线起始点的位置
        int row = 0;//斜线的开始位置的横坐标
        int col = str2.length() - 1;//斜线的结束位置的纵坐标
        while(row < str1.length()){
            int i = row;
            int j = col;
            while(i < str1.length() && j < str2.length()){
                if (str1.charAt(i) == str2.charAt(j)) {
                    preLen++;
                }else{
                    preLen = 0;
                }
                if (preLen > max) {
                    ends = i;
                    max = preLen;
                }
                i++;
                j++;
            }
            if (col > 0) {//列先向左移动
                col--;
            }else{//列移动到最左后，行向下移动
                row++;
            }
        }
        return str1.substring(ends - max + 1, ends + 1);
    }
}
